package leetcode;
import java.util.List;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
public class leetcode15三数之和 {
	/* 
	 * 这个题 用回溯 算法   TLE 了
	 * 滑动窗口And双指针.双指针 法  或者 哈希表
	 */
	
	public static void main(String []args) {
		int nums []= {-1,0,1,2,-1,-4};
		Deque<Integer> path =new ArrayDeque<>();
		List<List<Integer>> ans = new ArrayList<>();
		Arrays.sort(nums);
		process(nums,0,0,path,ans);
		System.out.println(ans);
	}
	// 滑动窗口And双指针.双指针   怎么收集 和去重 呢
	public static List<List<Integer>> solution(int nums[]){
		List<List<Integer>> ans=new ArrayList<>();
//		List<Integer> path =new ArrayList<>();
		Arrays.sort(nums);
//		int left=0;
//		int right=nums.length;
		for(int i=0;i < nums.length;i++) {
			if(nums[i] > 0) {
				return ans;
			}
			//  这个去重  还是 那个 集合之间的属于关系 后面的是前面的子集 所以 前一个 已经把 
			// 后一个 的相同的 数值的结果 找完了
			if(i > 0 && nums[i-1]==nums[i]) {
				continue;
			}
			int left=i+1;
			int right=nums.length-1;
			while(left < right) {
				int sum=nums[i]+nums[left]+nums[right];
				if(sum>0) {
					right--;
				}
				else if(sum<0) {
					left++;
				}
				else {
					ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
				}
				while(left < right && nums[right]==nums[right-1] ) {
					right--;
				}
				while(left < right && nums[left] == nums[left+1]) {
					left++;
				}
				right--;
				left++;
			}
		}
		
		return ans;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	// 回溯
	public static void process(int nums[],int index,int sum,Deque<Integer> path,List<List<Integer>> 
	ans) {
		if(sum>0 ||path.size()>3) {
			return ;
		}
		if(sum==0 && path.size()==3) {
			ans.add(new ArrayList<>(path));
			return ;
		}
		// 这里的 剪枝 可以有两种操作  int i= index;i < nums.length && path.size()<3;i++
		for(int i= index;i < nums.length;i++) {
			if(path.size()==3) {
				break;
			}
			if(i>index && nums[i]==nums[i-1]) {
				continue;
			}
//			if() {
//				
//			}
			path.addLast(nums[i]);
			process(nums,i+1,sum+nums[i],path,ans);
			path.removeLast();
		}
		
	}
}
